package com.topcoder.srm513;

import java.util.Arrays;

public class YetAnotherIncredibleMachine {
	private final static int M = 1000000009;

	public int countWays(int[] platformMount, int[] platformLength, int[] balls) {
		long total = 1;
		Arrays.sort(balls);
		for (int i = 0; i < platformMount.length; i++) {
			int way = way(platformMount[i], platformLength[i], balls);
			if (way == 0)
				return 0;
			total = (total * way) % M;
		}
		return (int) total;
	}

	private int way(int mount, int length, int[] balls) {
		int left = mount - length;
		int maxRight = mount + length + 1;
		int i = 0;
		int way = 0;
		while (left <= mount && i < balls.length) {
			int right = left + length;
			if (left > balls[i]) {
				i++;
				continue;
			}

			if (right < balls[i]) {
				way += Math.min(balls[i], maxRight) - right;
			}

			left = balls[i] + 1;
			i++;
		}

		return left < mount ? way + mount - left + 1 : way;
	}

	public int countWaysEgor(int[] platformMount, int[] platformLength,
			int[] balls) {
		Arrays.sort(balls);
		long result = 1;
		for (int i = 0; i < platformMount.length; i++) {
			int leftEnd = platformMount[i] - platformLength[i];
			int rightEnd = platformMount[i] + platformLength[i];
			for (int x : balls) {
				if (x >= platformMount[i])
					rightEnd = Math.min(rightEnd, x - 1);
				else
					leftEnd = Math.max(leftEnd, x + 1);
			}
			result = result * Math.max(rightEnd - leftEnd - platformLength[i] + 1, 0) % 1000000009;
		}
		return (int) result;
	}
}
